def _permute(L, nexts, numbers, begin, end):
    if end == begin + 1:
        yield L
    else:
        for i in range(begin, end):
            c = L[i]
            if nexts[c][0] == numbers[c]:
                nexts[c][0] += 1
                L[begin], L[i] = L[i], L[begin]
                for p in _permute(L, nexts, numbers, begin + 1, end):
                    yield p
                L[begin], L[i] = L[i], L[begin]
                nexts[c][0] -= 1


def constrained_permutations(L, constraints):
    # warning: assumes that L has unique, hashable elements
    # constraints is a list of constraints, where each constraint is a list of elements which should appear in the permatation in that order
    # warning: constraints may not overlap!
    nexts = dict((a, [0]) for a in L)
    numbers = dict.fromkeys(L, 0) # number of each element in its constraint
    for constraint in constraints:
        for i, pos in enumerate(constraint):
            nexts[pos] = nexts[constraint[0]]
            numbers[pos] = i

    for p in _permute(L, nexts, numbers, 0, len(L)):
        yield p

#===============================================================================
# L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# constraints = [[1, 3, 5, 7, 9], [2, 4, 6, 8, 10]]
# 
# L = ['p1', 'p2', 'q1', 'q2',]
# constraints = [['p1', 'p2'], ['q1','q2']]
# 
# A = list(p[:] for p in constrained_permutations(L, constraints)) # copy the permutation if you want to keep it
# print(len(A))
# print(["".join(map(str, p)) for p in A[:50]])
# print A
#===============================================================================

def createWorstCaseFsm(outputMessages, inputMessages, numberOfStates):
    fsm = {}
    
    for i in range(numberOfStates):
        currentState = "S" + str(i)
        for message in outputMessages:
            for j in range(numberOfStates):
                #if j != i:
                if not fsm.has_key((message, currentState)):
                    fsm[(message, currentState)] = set()
                fsm[(message, currentState)].add("S" + str(j))
                    
        for message in inputMessages:
            for j in range(numberOfStates):
                #if j != i:
                if not fsm.has_key((message, currentState)):
                    fsm[(message, currentState)] = set()
                fsm[(message, currentState)].add("S" + str(j))
    return fsm

def compressFsmLabels(fsm):
    newFsm = {}
    for key1 in fsm:
        newMessageLabel = set()
        #newMessageLabel.add(key1[0])
        for key2 in fsm:
            if key1[1] == key2[1] and fsm[key1] == fsm[key2]:
                newMessageLabel.add(key2[0])
        condition = False
        for key in newFsm:
            
            setFromKey = set(key[0].split(','))
            condition = (newMessageLabel == setFromKey) and key[1] == key1[1]
        if not condition:
            newMessageLabelString = ''
            for element in newMessageLabel:
                newMessageLabelString += "" + element + ","
            newMessageLabelString = newMessageLabelString[:-1]
            newFsm[(newMessageLabelString, key1[1])] = fsm[key1]
    
    
    return newFsm

def generateDotFile(outputFile, fsm):
    f = open(outputFile, 'w')
    
    f.write('digraph G {\n')
    for key in fsm:
        for nextStates in fsm[key]:

            f.write('    ' + key[1] + ' -> ' + nextStates + ' [label="' + key[0] + '"];\n')
    f.write('}\n')
    f.close()
            
fsm = createWorstCaseFsm(['-p0', '-p2', '-p4', '-p6', '-p8'], ['+q1', '+q3', '+q5', '+q7', '+q9'], 100)
#fsm = compressFsmLabels(fsm)
generateDotFile('worstCase.fsm', fsm)